/**
 * @license Copyright (c) 2003-2023, CKSource Holding sp. z o.o. All rights reserved.
 * For licensing, see LICENSE.md or https://ckeditor.com/legal/ckeditor-oss-license
 */
import InsertOperation from './insertoperation';
import AttributeOperation from './attributeoperation';
import RenameOperation from './renameoperation';
import MarkerOperation from './markeroperation';
import MoveOperation from './moveoperation';
import RootAttributeOperation from './rootattributeoperation';
import RootOperation from './rootoperation';
import MergeOperation from './mergeoperation';
import SplitOperation from './splitoperation';
import NoOperation from './nooperation';
import Range from '../range';
import Position from '../position';
import { compareArrays } from '@ckeditor/ckeditor5-utils';
const transformations = new Map();
/**
 * @module engine/model/operation/transform
 */
/**
 * Sets a transformation function to be be used to transform instances of class `OperationA` by instances of class `OperationB`.
 *
 * The `transformationFunction` is passed three parameters:
 *
 * * `a` - operation to be transformed, an instance of `OperationA`,
 * * `b` - operation to be transformed by, an instance of `OperationB`,
 * * {@link module:engine/model/operation/transform~TransformationContext `context`} - object with additional information about
 * transformation context.
 *
 * The `transformationFunction` should return transformation result, which is an array with one or multiple
 * {@link module:engine/model/operation/operation~Operation operation} instances.
 *
 * @param transformationFunction Function to use for transforming.
 */
function setTransformation(OperationA, OperationB, transformationFunction) {
    let aGroup = transformations.get(OperationA);
    if (!aGroup) {
        aGroup = new Map();
        transformations.set(OperationA, aGroup);
    }
    aGroup.set(OperationB, transformationFunction);
}
/**
 * Returns a previously set transformation function for transforming an instance of `OperationA` by an instance of `OperationB`.
 *
 * If no transformation was set for given pair of operations, {@link module:engine/model/operation/transform~noUpdateTransformation}
 * is returned. This means that if no transformation was set, the `OperationA` instance will not change when transformed
 * by the `OperationB` instance.
 *
 * @returns Function set to transform an instance of `OperationA` by an instance of `OperationB`.
 */
function getTransformation(OperationA, OperationB) {
    const aGroup = transformations.get(OperationA);
    if (aGroup && aGroup.has(OperationB)) {
        return aGroup.get(OperationB);
    }
    return noUpdateTransformation;
}
/**
 * A transformation function that only clones operation to transform, without changing it.
 */
function noUpdateTransformation(a) {
    return [a];
}
/**
 * Transforms operation `a` by operation `b`.
 *
 * @param a Operation to be transformed.
 * @param b Operation to transform by.
 * @param context Transformation context for this transformation.
 * @returns Transformation result.
 */
export function transform(a, b, context = {}) {
    const transformationFunction = getTransformation(a.constructor, b.constructor);
    /* eslint-disable no-useless-catch */
    try {
        a = a.clone();
        return transformationFunction(a, b, context);
    }
    catch (e) {
        // @if CK_DEBUG // console.warn( 'Error during operation transformation!', e.message );
        // @if CK_DEBUG // console.warn( 'Transformed operation', a );
        // @if CK_DEBUG // console.warn( 'Operation transformed by', b );
        // @if CK_DEBUG // console.warn( 'context.aIsStrong', context.aIsStrong );
        // @if CK_DEBUG // console.warn( 'context.aWasUndone', context.aWasUndone );
        // @if CK_DEBUG // console.warn( 'context.bWasUndone', context.bWasUndone );
        // @if CK_DEBUG // console.warn( 'context.abRelation', context.abRelation );
        // @if CK_DEBUG // console.warn( 'context.baRelation', context.baRelation );
        throw e;
    }
    /* eslint-enable no-useless-catch */
}
/**
 * Performs a transformation of two sets of operations - `operationsA` and `operationsB`. The transformation is two-way -
 * both transformed `operationsA` and transformed `operationsB` are returned.
 *
 * Note, that the first operation in each set should base on the same document state (
 * {@link module:engine/model/document~Document#version document version}).
 *
 * It is assumed that `operationsA` are "more important" during conflict resolution between two operations.
 *
 * New copies of both passed arrays and operations inside them are returned. Passed arguments are not altered.
 *
 * Base versions of the transformed operations sets are updated accordingly. For example, assume that base versions are `4`
 * and there are `3` operations in `operationsA` and `5` operations in `operationsB`. Then:
 *
 * * transformed `operationsA` will start from base version `9` (`4` base version + `5` operations B),
 * * transformed `operationsB` will start from base version `7` (`4` base version + `3` operations A).
 *
 * If no operation was broken into two during transformation, then both sets will end up with an operation that bases on version `11`:
 *
 * * transformed `operationsA` start from `9` and there are `3` of them, so the last will have `baseVersion` equal to `11`,
 * * transformed `operationsB` start from `7` and there are `5` of them, so the last will have `baseVersion` equal to `11`.
 *
 * @param operationsA
 * @param operationsB
 * @param options Additional transformation options.
 * @param options.document Document which the operations change.
 * @param options.useRelations Whether during transformation relations should be used (used during undo for better conflict resolution).
 * @param options.padWithNoOps Whether additional {@link module:engine/model/operation/nooperation~NoOperation}s
 * should be added to the transformation results to force the same last base version for both transformed sets (in case
 * if some operations got broken into multiple operations during transformation).
 * @param options.forceWeakRemove If set to `false`, remove operation will be always stronger than move operation,
 * so the removed nodes won't end up back in the document root. When set to `true`, context data will be used.
 * @returns Transformation result.
 */
export function transformSets(operationsA, operationsB, options) {
    // Create new arrays so the originally passed arguments are not changed.
    // No need to clone operations, they are cloned as they are transformed.
    operationsA = operationsA.slice();
    operationsB = operationsB.slice();
    const contextFactory = new ContextFactory(options.document, options.useRelations, options.forceWeakRemove);
    contextFactory.setOriginalOperations(operationsA);
    contextFactory.setOriginalOperations(operationsB);
    const originalOperations = contextFactory.originalOperations;
    // If one of sets is empty there is simply nothing to transform, so return sets as they are.
    if (operationsA.length == 0 || operationsB.length == 0) {
        return { operationsA, operationsB, originalOperations };
    }
    //
    // Following is a description of transformation process:
    //
    // There are `operationsA` and `operationsB` to be transformed, both by both.
    //
    // So, suppose we have sets of two operations each: `operationsA` = `[ a1, a2 ]`, `operationsB` = `[ b1, b2 ]`.
    //
    // Remember, that we can only transform operations that base on the same context. We assert that `a1` and `b1` base on
    // the same context and we transform them. Then, we get `a1'` and `b1'`. `a2` bases on a context with `a1` -- `a2`
    // is an operation that followed `a1`. Similarly, `b2` bases on a context with `b1`.
    //
    // However, since `a1'` is a result of transformation by `b1`, `a1'` now also has a context with `b1`. This means that
    // we can safely transform `a1'` by `b2`. As we finish transforming `a1`, we also transformed all `operationsB`.
    // All `operationsB` also have context including `a1`. Now, we can properly transform `a2` by those operations.
    //
    // The transformation process can be visualized on a transformation diagram ("diamond diagram"):
    //
    //          [the initial state]
    //         [common for a1 and b1]
    //
    //                   *
    //                  / \
    //                 /   \
    //               b1     a1
    //               /       \
    //              /         \
    //             *           *
    //            / \         / \
    //           /   \       /   \
    //         b2    a1'   b1'    a2
    //         /       \   /       \
    //        /         \ /         \
    //       *           *           *
    //        \         / \         /
    //         \       /   \       /
    //        a1''   b2'   a2'   b1''
    //           \   /       \   /
    //            \ /         \ /
    //             *           *
    //              \         /
    //               \       /
    //              a2''   b2''
    //                 \   /
    //                  \ /
    //                   *
    //
    //           [the final state]
    //
    // The final state can be reached from the initial state by applying `a1`, `a2`, `b1''` and `b2''`, as well as by
    // applying `b1`, `b2`, `a1''`, `a2''`. Note how the operations get to a proper common state before each pair is
    // transformed.
    //
    // Another thing to consider is that an operation during transformation can be broken into multiple operations.
    // Suppose that `a1` * `b1` = `[ a11', a12' ]` (instead of `a1'` that we considered previously).
    //
    // In that case, we leave `a12'` for later and we continue transforming `a11'` until it is transformed by all `operationsB`
    // (in our case it is just `b2`). At this point, `b1` is transformed by "whole" `a1`, while `b2` is only transformed
    // by `a11'`. Similarly, `a12'` is only transformed by `b1`. This leads to a conclusion that we need to start transforming `a12'`
    // from the moment just after it was broken. So, `a12'` is transformed by `b2`. Now, "the whole" `a1` is transformed
    // by `operationsB`, while all `operationsB` are transformed by "the whole" `a1`. This means that we can continue with
    // following `operationsA` (in our case it is just `a2`).
    //
    // Of course, also `operationsB` can be broken. However, since we focus on transforming operation `a` to the end,
    // the only thing to do is to store both pieces of operation `b`, so that the next transformed operation `a` will
    // be transformed by both of them.
    //
    //                       *
    //                      / \
    //                     /   \
    //                    /     \
    //                  b1       a1
    //                  /         \
    //                 /           \
    //                /             \
    //               *               *
    //              / \             / \
    //             /  a11'         /   \
    //            /     \         /     \
    //          b2       *      b1'      a2
    //          /       / \     /         \
    //         /       /  a12' /           \
    //        /       /     \ /             \
    //       *       b2'     *               *
    //        \     /       / \             /
    //       a11'' /     b21'' \           /
    //          \ /       /     \         /
    //           *       *      a2'     b1''
    //            \     / \       \     /
    //          a12'' b22''\       \   /
    //              \ /     \       \ /
    //               *      a2''     *
    //                \       \     /
    //                 \       \  b21'''
    //                  \       \ /
    //                a2'''      *
    //                    \     /
    //                     \  b22'''
    //                      \ /
    //                       *
    //
    // Note, how `a1` is broken and transformed into `a11'` and `a12'`, while `b2'` got broken and transformed into `b21''` and `b22''`.
    //
    // Having all that on mind, here is an outline for the transformation process algorithm:
    //
    // 1. We have `operationsA` and `operationsB` array, which we dynamically update as the transformation process goes.
    //
    // 2. We take next (or first) operation from `operationsA` and check from which operation `b` we need to start transforming it.
    // All original `operationsA` are set to be transformed starting from the first operation `b`.
    //
    // 3. We take operations from `operationsB`, one by one, starting from the correct one, and transform operation `a`
    // by operation `b` (and vice versa). We update `operationsA` and `operationsB` by replacing the original operations
    // with the transformation results.
    //
    // 4. If operation is broken into multiple operations, we save all the new operations in the place of the
    // original operation.
    //
    // 5. Additionally, if operation `a` was broken, for the "new" operation, we remember from which operation `b` it should
    // be transformed by.
    //
    // 6. We continue transforming "current" operation `a` until it is transformed by all `operationsB`. Then, go to 2.
    // unless the last operation `a` was transformed.
    //
    // The actual implementation of the above algorithm is slightly different, as only one loop (while) is used.
    // The difference is that we have "current" `a` operation to transform and we store the index of the next `b` operation
    // to transform by. Each loop operates on two indexes then: index pointing to currently processed `a` operation and
    // index pointing to next `b` operation. Each loop is just one `a * b` + `b * a` transformation. After each loop
    // operation `b` index is updated. If all `b` operations were visited for the current `a` operation, we change
    // current `a` operation index to the next one.
    //
    // For each operation `a`, keeps information what is the index in `operationsB` from which the transformation should start.
    const nextTransformIndex = new WeakMap();
    // For all the original `operationsA`, set that they should be transformed starting from the first of `operationsB`.
    for (const op of operationsA) {
        nextTransformIndex.set(op, 0);
    }
    // Additional data that is used for some postprocessing after the main transformation process is done.
    const data = {
        nextBaseVersionA: operationsA[operationsA.length - 1].baseVersion + 1,
        nextBaseVersionB: operationsB[operationsB.length - 1].baseVersion + 1,
        originalOperationsACount: operationsA.length,
        originalOperationsBCount: operationsB.length
    };
    // Index of currently transformed operation `a`.
    let i = 0;
    // While not all `operationsA` are transformed...
    while (i < operationsA.length) {
        // Get "current" operation `a`.
        const opA = operationsA[i];
        // For the "current" operation `a`, get the index of the next operation `b` to transform by.
        const indexB = nextTransformIndex.get(opA);
        // If operation `a` was already transformed by every operation `b`, change "current" operation `a` to the next one.
        if (indexB == operationsB.length) {
            i++;
            continue;
        }
        const opB = operationsB[indexB];
        // Transform `a` by `b` and `b` by `a`.
        const newOpsA = transform(opA, opB, contextFactory.getContext(opA, opB, true));
        const newOpsB = transform(opB, opA, contextFactory.getContext(opB, opA, false));
        // As a result we get one or more `newOpsA` and one or more `newOpsB` operations.
        // Update contextual information about operations.
        contextFactory.updateRelation(opA, opB);
        contextFactory.setOriginalOperations(newOpsA, opA);
        contextFactory.setOriginalOperations(newOpsB, opB);
        // For new `a` operations, update their index of the next operation `b` to transform them by.
        //
        // This is needed even if there was only one result (`a` was not broken) because that information is used
        // at the beginning of this loop every time.
        for (const newOpA of newOpsA) {
            // Acknowledge, that operation `b` also might be broken into multiple operations.
            //
            // This is why we raise `indexB` not just by 1. If `newOpsB` are multiple operations, they will be
            // spliced in the place of `opB`. So we need to change `transformBy` accordingly, so that an operation won't
            // be transformed by the same operation (part of it) again.
            nextTransformIndex.set(newOpA, indexB + newOpsB.length);
        }
        // Update `operationsA` and `operationsB` with the transformed versions.
        operationsA.splice(i, 1, ...newOpsA);
        operationsB.splice(indexB, 1, ...newOpsB);
    }
    if (options.padWithNoOps) {
        // If no-operations padding is enabled, count how many extra `a` and `b` operations were generated.
        const brokenOperationsACount = operationsA.length - data.originalOperationsACount;
        const brokenOperationsBCount = operationsB.length - data.originalOperationsBCount;
        // Then, if that number is not the same, pad `operationsA` or `operationsB` with correct number of no-ops so
        // that the base versions are equalled.
        //
        // Note that only one array will be updated, as only one of those subtractions can be greater than zero.
        padWithNoOps(operationsA, brokenOperationsBCount - brokenOperationsACount);
        padWithNoOps(operationsB, brokenOperationsACount - brokenOperationsBCount);
    }
    // Finally, update base versions of transformed operations.
    updateBaseVersions(operationsA, data.nextBaseVersionB);
    updateBaseVersions(operationsB, data.nextBaseVersionA);
    return { operationsA, operationsB, originalOperations };
}
/**
 * Gathers additional data about operations processed during transformation. Can be used to obtain contextual information
 * about two operations that are about to be transformed. This contextual information can be used for better conflict resolution.
 */
class ContextFactory {
    /**
     * Creates `ContextFactory` instance.
     *
     * @param document Document which the operations change.
     * @param useRelations Whether during transformation relations should be used (used during undo for
     * better conflict resolution).
     * @param forceWeakRemove If set to `false`, remove operation will be always stronger than move operation,
     * so the removed nodes won't end up back in the document root. When set to `true`, context data will be used.
     */
    constructor(document, useRelations, forceWeakRemove = false) {
        // For each operation that is created during transformation process, we keep a reference to the original operation
        // which it comes from. The original operation works as a kind of "identifier". Every contextual information
        // gathered during transformation that we want to save for given operation, is actually saved for the original operation.
        // This way no matter if operation `a` is cloned, then transformed, even breaks, we still have access to the previously
        // gathered data through original operation reference.
        this.originalOperations = new Map();
        // `model.History` instance which information about undone operations will be taken from.
        this._history = document.history;
        // Whether additional context should be used.
        this._useRelations = useRelations;
        this._forceWeakRemove = !!forceWeakRemove;
        // Relations is a double-map structure (maps in map) where for two operations we store how those operations were related
        // to each other. Those relations are evaluated during transformation process. For every transformated pair of operations
        // we keep relations between them.
        this._relations = new Map();
    }
    /**
     * Sets "original operation" for given operations.
     *
     * During transformation process, operations are cloned, then changed, then processed again, sometimes broken into two
     * or multiple operations. When gathering additional data it is important that all operations can be somehow linked
     * so a cloned and transformed "version" still kept track of the data assigned earlier to it.
     *
     * The original operation object will be used as such an universal linking id. Throughout the transformation process
     * all cloned operations will refer to "the original operation" when storing and reading additional data.
     *
     * If `takeFrom` is not set, each operation from `operations` array will be assigned itself as "the original operation".
     * This should be used as an initialization step.
     *
     * If `takeFrom` is set, each operation from `operations` will be assigned the same original operation as assigned
     * for `takeFrom` operation. This should be used to update original operations. It should be used in a way that
     * `operations` are the result of `takeFrom` transformation to ensure proper "original operation propagation".
     */
    setOriginalOperations(operations, takeFrom = null) {
        const originalOperation = takeFrom ? this.originalOperations.get(takeFrom) : null;
        for (const operation of operations) {
            this.originalOperations.set(operation, originalOperation || operation);
        }
    }
    /**
     * Saves a relation between operations `opA` and `opB`.
     *
     * Relations are then later used to help solve conflicts when operations are transformed.
     */
    updateRelation(opA, opB) {
        // The use of relations is described in a bigger detail in transformation functions.
        //
        // In brief, this function, for specified pairs of operation types, checks how positions defined in those operations relate.
        // Then those relations are saved. For example, for two move operations, it is saved if one of those operations target
        // position is before the other operation source position. This kind of information gives contextual information when
        // transformation is used during undo. Similar checks are done for other pairs of operations.
        //
        if (opA instanceof MoveOperation) {
            if (opB instanceof MergeOperation) {
                if (opA.targetPosition.isEqual(opB.sourcePosition) || opB.movedRange.containsPosition(opA.targetPosition)) {
                    this._setRelation(opA, opB, 'insertAtSource');
                }
                else if (opA.targetPosition.isEqual(opB.deletionPosition)) {
                    this._setRelation(opA, opB, 'insertBetween');
                }
                else if (opA.targetPosition.isAfter(opB.sourcePosition)) {
                    this._setRelation(opA, opB, 'moveTargetAfter');
                }
            }
            else if (opB instanceof MoveOperation) {
                if (opA.targetPosition.isEqual(opB.sourcePosition) || opA.targetPosition.isBefore(opB.sourcePosition)) {
                    this._setRelation(opA, opB, 'insertBefore');
                }
                else {
                    this._setRelation(opA, opB, 'insertAfter');
                }
            }
        }
        else if (opA instanceof SplitOperation) {
            if (opB instanceof MergeOperation) {
                if (opA.splitPosition.isBefore(opB.sourcePosition)) {
                    this._setRelation(opA, opB, 'splitBefore');
                }
            }
            else if (opB instanceof MoveOperation) {
                if (opA.splitPosition.isEqual(opB.sourcePosition) || opA.splitPosition.isBefore(opB.sourcePosition)) {
                    this._setRelation(opA, opB, 'splitBefore');
                }
                else {
                    const range = Range._createFromPositionAndShift(opB.sourcePosition, opB.howMany);
                    if (opA.splitPosition.hasSameParentAs(opB.sourcePosition) && range.containsPosition(opA.splitPosition)) {
                        const howMany = range.end.offset - opA.splitPosition.offset;
                        const offset = opA.splitPosition.offset - range.start.offset;
                        this._setRelation(opA, opB, { howMany, offset });
                    }
                }
            }
        }
        else if (opA instanceof MergeOperation) {
            if (opB instanceof MergeOperation) {
                if (!opA.targetPosition.isEqual(opB.sourcePosition)) {
                    this._setRelation(opA, opB, 'mergeTargetNotMoved');
                }
                if (opA.sourcePosition.isEqual(opB.targetPosition)) {
                    this._setRelation(opA, opB, 'mergeSourceNotMoved');
                }
                if (opA.sourcePosition.isEqual(opB.sourcePosition)) {
                    this._setRelation(opA, opB, 'mergeSameElement');
                }
            }
            else if (opB instanceof SplitOperation) {
                if (opA.sourcePosition.isEqual(opB.splitPosition)) {
                    this._setRelation(opA, opB, 'splitAtSource');
                }
            }
        }
        else if (opA instanceof MarkerOperation) {
            const markerRange = opA.newRange;
            if (!markerRange) {
                return;
            }
            if (opB instanceof MoveOperation) {
                const movedRange = Range._createFromPositionAndShift(opB.sourcePosition, opB.howMany);
                const affectedLeft = movedRange.containsPosition(markerRange.start) ||
                    movedRange.start.isEqual(markerRange.start);
                const affectedRight = movedRange.containsPosition(markerRange.end) ||
                    movedRange.end.isEqual(markerRange.end);
                if ((affectedLeft || affectedRight) && !movedRange.containsRange(markerRange)) {
                    this._setRelation(opA, opB, {
                        side: affectedLeft ? 'left' : 'right',
                        path: affectedLeft ? markerRange.start.path.slice() : markerRange.end.path.slice()
                    });
                }
            }
            else if (opB instanceof MergeOperation) {
                const wasInLeftElement = markerRange.start.isEqual(opB.targetPosition);
                const wasStartBeforeMergedElement = markerRange.start.isEqual(opB.deletionPosition);
                const wasEndBeforeMergedElement = markerRange.end.isEqual(opB.deletionPosition);
                const wasInRightElement = markerRange.end.isEqual(opB.sourcePosition);
                if (wasInLeftElement || wasStartBeforeMergedElement || wasEndBeforeMergedElement || wasInRightElement) {
                    this._setRelation(opA, opB, {
                        wasInLeftElement,
                        wasStartBeforeMergedElement,
                        wasEndBeforeMergedElement,
                        wasInRightElement
                    });
                }
            }
        }
    }
    /**
     * Evaluates and returns contextual information about two given operations `opA` and `opB` which are about to be transformed.
     */
    getContext(opA, opB, aIsStrong) {
        return {
            aIsStrong,
            aWasUndone: this._wasUndone(opA),
            bWasUndone: this._wasUndone(opB),
            abRelation: this._useRelations ? this._getRelation(opA, opB) : null,
            baRelation: this._useRelations ? this._getRelation(opB, opA) : null,
            forceWeakRemove: this._forceWeakRemove
        };
    }
    /**
     * Returns whether given operation `op` has already been undone.
     *
     * Information whether an operation was undone gives more context when making a decision when two operations are in conflict.
     */
    _wasUndone(op) {
        // For `op`, get its original operation. After all, if `op` is a clone (or even transformed clone) of another
        // operation, literally `op` couldn't be undone. It was just generated. If anything, it was the operation it origins
        // from which was undone. So get that original operation.
        const originalOp = this.originalOperations.get(op);
        // And check with the document if the original operation was undone.
        return originalOp.wasUndone || this._history.isUndoneOperation(originalOp);
    }
    /**
     * Returns a relation between `opA` and an operation which is undone by `opB`. This can be `String` value if a relation
     * was set earlier or `null` if there was no relation between those operations.
     *
     * This is a little tricky to understand, so let's compare it to `ContextFactory#_wasUndone`.
     *
     * When `wasUndone( opB )` is used, we check if the `opB` has already been undone. It is obvious, that the
     * undoing operation must happen after the undone operation. So, essentially, we have `opB`, we take document history,
     * we look forward in the future and ask if in that future `opB` was undone.
     *
     * Relations is a backward process to `wasUndone()`.
     *
     * Long story short - using relations is asking what happened in the past. Looking back. This time we have an undoing
     * operation `opB` which has undone some other operation. When there is a transformation `opA` x `opB` and there is
     * a conflict to solve and `opB` is an undoing operation, we can look back in the history and see what was a relation
     * between `opA` and the operation which `opB` undone. Basing on that relation from the past, we can now make
     * a better decision when resolving a conflict between two operations, because we know more about the context of
     * those two operations.
     *
     * This is why this function does not return a relation directly between `opA` and `opB` because we need to look
     * back to search for a meaningful contextual information.
     */
    _getRelation(opA, opB) {
        // Get the original operation. Similarly as in `wasUndone()` it is used as an universal identifier for stored data.
        const origB = this.originalOperations.get(opB);
        const undoneB = this._history.getUndoneOperation(origB);
        // If `opB` is not undoing any operation, there is no relation.
        if (!undoneB) {
            return null;
        }
        const origA = this.originalOperations.get(opA);
        const relationsA = this._relations.get(origA);
        // Get all relations for `opA`, and check if there is a relation with `opB`-undone-counterpart. If so, return it.
        if (relationsA) {
            return relationsA.get(undoneB) || null;
        }
        return null;
    }
    /**
     * Helper function for `ContextFactory#updateRelations`.
     */
    _setRelation(opA, opB, relation) {
        // As always, setting is for original operations, not the clones/transformed operations.
        const origA = this.originalOperations.get(opA);
        const origB = this.originalOperations.get(opB);
        let relationsA = this._relations.get(origA);
        if (!relationsA) {
            relationsA = new Map();
            this._relations.set(origA, relationsA);
        }
        relationsA.set(origB, relation);
    }
}
/**
 * An utility function that updates {@link module:engine/model/operation/operation~Operation#baseVersion base versions}
 * of passed operations.
 *
 * The function simply sets `baseVersion` as a base version of the first passed operation and then increments it for
 * each following operation in `operations`.
 *
 * @param operations Operations to update.
 * @param baseVersion Base version to set for the first operation in `operations`.
 */
function updateBaseVersions(operations, baseVersion) {
    for (const operation of operations) {
        operation.baseVersion = baseVersion++;
    }
}
/**
 * Adds `howMany` instances of {@link module:engine/model/operation/nooperation~NoOperation} to `operations` set.
 */
function padWithNoOps(operations, howMany) {
    for (let i = 0; i < howMany; i++) {
        operations.push(new NoOperation(0));
    }
}
// -----------------------
setTransformation(AttributeOperation, AttributeOperation, (a, b, context) => {
    // If operations in conflict, check if their ranges intersect and manage them properly.
    //
    // Operations can be in conflict only if:
    //
    // * their key is the same (they change the same attribute), and
    // * they are in the same parent (operations for ranges [ 1 ] - [ 3 ] and [ 2, 0 ] - [ 2, 5 ] change different
    // elements and can't be in conflict).
    if (a.key === b.key && a.range.start.hasSameParentAs(b.range.start)) {
        // First, we want to apply change to the part of a range that has not been changed by the other operation.
        const operations = a.range.getDifference(b.range).map(range => {
            return new AttributeOperation(range, a.key, a.oldValue, a.newValue, 0);
        });
        // Then we take care of the common part of ranges.
        const common = a.range.getIntersection(b.range);
        if (common) {
            // If this operation is more important, we also want to apply change to the part of the
            // original range that has already been changed by the other operation. Since that range
            // got changed we also have to update `oldValue`.
            if (context.aIsStrong) {
                operations.push(new AttributeOperation(common, b.key, b.newValue, a.newValue, 0));
            }
        }
        if (operations.length == 0) {
            return [new NoOperation(0)];
        }
        return operations;
    }
    else {
        // If operations don't conflict, simply return an array containing just a clone of this operation.
        return [a];
    }
});
setTransformation(AttributeOperation, InsertOperation, (a, b) => {
    // Case 1:
    //
    // The attribute operation range includes the position where nodes were inserted.
    // There are two possible scenarios: the inserted nodes were text and they should receive attributes or
    // the inserted nodes were elements and they should not receive attributes.
    //
    if (a.range.start.hasSameParentAs(b.position) && a.range.containsPosition(b.position)) {
        // If new nodes should not receive attributes, two separated ranges will be returned.
        // Otherwise, one expanded range will be returned.
        const range = a.range._getTransformedByInsertion(b.position, b.howMany, !b.shouldReceiveAttributes);
        const result = range.map(r => {
            return new AttributeOperation(r, a.key, a.oldValue, a.newValue, a.baseVersion);
        });
        if (b.shouldReceiveAttributes) {
            // `AttributeOperation#range` includes some newly inserted text.
            // The operation should also change the attribute of that text. An example:
            //
            // Bold should be applied on the following range:
            // <p>Fo[zb]ar</p>
            //
            // In meantime, new text is typed:
            // <p>Fozxxbar</p>
            //
            // Bold should be applied also on the new text:
            // <p>Fo[zxxb]ar</p>
            // <p>Fo<$text bold="true">zxxb</$text>ar</p>
            //
            // There is a special case to consider here to consider.
            //
            // Consider setting an attribute with multiple possible values, for example `highlight`. The inserted text might
            // have already an attribute value applied and the `oldValue` property of the attribute operation might be wrong:
            //
            // Attribute `highlight="yellow"` should be applied on the following range:
            // <p>Fo[zb]ar<p>
            //
            // In meantime, character `x` with `highlight="red"` is typed:
            // <p>Fo[z<$text highlight="red">x</$text>b]ar</p>
            //
            // In this case we cannot simply apply operation changing the attribute value from `null` to `"yellow"` for the whole range
            // because that would lead to an exception (`oldValue` is incorrect for `x`).
            //
            // We also cannot break the original range as this would mess up a scenario when there are multiple following
            // insert operations, because then only the first inserted character is included in those ranges:
            // <p>Fo[z][x][b]ar</p>   -->   <p>Fo[z][x]x[b]ar</p>   -->   <p>Fo[z][x]xx[b]ar</p>
            //
            // So, the attribute range needs be expanded, no matter what attributes are set on the inserted nodes:
            //
            // <p>Fo[z<$text highlight="red">x</$text>b]ar</p>      <--- Change from `null` to `yellow`, throwing an exception.
            //
            // But before that operation would be applied, we will add an additional attribute operation that will change
            // attributes on the inserted nodes in a way which would make the original operation correct:
            //
            // <p>Fo[z{<$text highlight="red">}x</$text>b]ar</p>    <--- Change range `{}` from `red` to `null`.
            // <p>Fo[zxb]ar</p>                                     <--- Now change from `null` to `yellow` is completely fine.
            //
            // Generate complementary attribute operation. Be sure to add it before the original operation.
            const op = _getComplementaryAttributeOperations(b, a.key, a.oldValue);
            if (op) {
                result.unshift(op);
            }
        }
        // If nodes should not receive new attribute, we are done here.
        return result;
    }
    // If insert operation is not expanding the attribute operation range, simply transform the range.
    a.range = a.range._getTransformedByInsertion(b.position, b.howMany, false)[0];
    return [a];
});
/**
 * Helper function for `AttributeOperation` x `InsertOperation` (and reverse) transformation.
 *
 * For given `insertOperation` it checks the inserted node if it has an attribute `key` set to a value different
 * than `newValue`. If so, it generates an `AttributeOperation` which changes the value of `key` attribute to `newValue`.
 */
function _getComplementaryAttributeOperations(insertOperation, key, newValue) {
    const nodes = insertOperation.nodes;
    // At the beginning we store the attribute value from the first node.
    const insertValue = nodes.getNode(0).getAttribute(key);
    if (insertValue == newValue) {
        return null;
    }
    const range = new Range(insertOperation.position, insertOperation.position.getShiftedBy(insertOperation.howMany));
    return new AttributeOperation(range, key, insertValue, newValue, 0);
}
setTransformation(AttributeOperation, MergeOperation, (a, b) => {
    const ranges = [];
    // Case 1:
    //
    // Attribute change on the merged element. In this case, the merged element was moved to the graveyard.
    // An additional attribute operation that will change the (re)moved element needs to be generated.
    //
    if (a.range.start.hasSameParentAs(b.deletionPosition)) {
        if (a.range.containsPosition(b.deletionPosition) || a.range.start.isEqual(b.deletionPosition)) {
            ranges.push(Range._createFromPositionAndShift(b.graveyardPosition, 1));
        }
    }
    const range = a.range._getTransformedByMergeOperation(b);
    // Do not add empty (collapsed) ranges to the result. `range` may be collapsed if it contained only the merged element.
    if (!range.isCollapsed) {
        ranges.push(range);
    }
    // Create `AttributeOperation`s out of the ranges.
    return ranges.map(range => {
        return new AttributeOperation(range, a.key, a.oldValue, a.newValue, a.baseVersion);
    });
});
setTransformation(AttributeOperation, MoveOperation, (a, b) => {
    const ranges = _breakRangeByMoveOperation(a.range, b);
    // Create `AttributeOperation`s out of the ranges.
    return ranges.map(range => new AttributeOperation(range, a.key, a.oldValue, a.newValue, a.baseVersion));
});
/**
 * Helper function for `AttributeOperation` x `MoveOperation` transformation.
 *
 * Takes the passed `range` and transforms it by move operation `moveOp` in a specific way. Only top-level nodes of `range`
 * are considered to be in the range. If move operation moves nodes deep from inside of the range, those nodes won't
 * be included in the result. In other words, top-level nodes of the ranges from the result are exactly the same as
 * top-level nodes of the original `range`.
 *
 * This is important for `AttributeOperation` because, for its range, it changes only the top-level nodes. So we need to
 * track only how those nodes have been affected by `MoveOperation`.
 */
function _breakRangeByMoveOperation(range, moveOp) {
    const moveRange = Range._createFromPositionAndShift(moveOp.sourcePosition, moveOp.howMany);
    // We are transforming `range` (original range) by `moveRange` (range moved by move operation). As usual when it comes to
    // transforming a ranges, we may have a common part of the ranges and we may have a difference part (zero to two ranges).
    let common = null;
    let difference = [];
    // Let's compare the ranges.
    if (moveRange.containsRange(range, true)) {
        // If the whole original range is moved, treat it whole as a common part. There's also no difference part.
        common = range;
    }
    else if (range.start.hasSameParentAs(moveRange.start)) {
        // If the ranges are "on the same level" (in the same parent) then move operation may move exactly those nodes
        // that are changed by the attribute operation. In this case we get common part and difference part in the usual way.
        difference = range.getDifference(moveRange);
        common = range.getIntersection(moveRange);
    }
    else {
        // In any other situation we assume that original range is different than move range, that is that move operation
        // moves other nodes that attribute operation change. Even if the moved range is deep inside in the original range.
        //
        // Note that this is different than in `.getIntersection` (we would get a common part in that case) and different
        // than `.getDifference` (we would get two ranges).
        difference = [range];
    }
    const result = [];
    // The default behaviour of `_getTransformedByMove` might get wrong results for difference part, though, so
    // we do it by hand.
    for (let diff of difference) {
        // First, transform the range by removing moved nodes. Since this is a difference, this is safe, `null` won't be returned
        // as the range is different than the moved range.
        diff = diff._getTransformedByDeletion(moveOp.sourcePosition, moveOp.howMany);
        // Transform also `targetPosition`.
        const targetPosition = moveOp.getMovedRangeStart();
        // Spread the range only if moved nodes are inserted only between the top-level nodes of the `diff` range.
        const spread = diff.start.hasSameParentAs(targetPosition);
        // Transform by insertion of moved nodes.
        const diffs = diff._getTransformedByInsertion(targetPosition, moveOp.howMany, spread);
        result.push(...diffs);
    }
    // Common part can be simply transformed by the move operation. This is because move operation will not target to
    // that common part (the operation would have to target inside its own moved range).
    if (common) {
        result.push(common._getTransformedByMove(moveOp.sourcePosition, moveOp.targetPosition, moveOp.howMany, false)[0]);
    }
    return result;
}
setTransformation(AttributeOperation, SplitOperation, (a, b) => {
    // Case 1:
    //
    // Split node is the last node in `AttributeOperation#range`.
    // `AttributeOperation#range` needs to be expanded to include the new (split) node.
    //
    // Attribute `type` to be changed to `numbered` but the `listItem` is split.
    // <listItem type="bulleted">foobar</listItem>
    //
    // After split:
    // <listItem type="bulleted">foo</listItem><listItem type="bulleted">bar</listItem>
    //
    // After attribute change:
    // <listItem type="numbered">foo</listItem><listItem type="numbered">foo</listItem>
    //
    if (a.range.end.isEqual(b.insertionPosition)) {
        if (!b.graveyardPosition) {
            a.range.end.offset++;
        }
        return [a];
    }
    // Case 2:
    //
    // Split position is inside `AttributeOperation#range`, at the same level, so the nodes to change are
    // not going to make a flat range.
    //
    // Content with range-to-change and split position:
    // <p>Fo[zb^a]r</p>
    //
    // After split:
    // <p>Fozb</p><p>ar</p>
    //
    // Make two separate ranges containing all nodes to change:
    // <p>Fo[zb]</p><p>[a]r</p>
    //
    if (a.range.start.hasSameParentAs(b.splitPosition) && a.range.containsPosition(b.splitPosition)) {
        const secondPart = a.clone();
        secondPart.range = new Range(b.moveTargetPosition.clone(), a.range.end._getCombined(b.splitPosition, b.moveTargetPosition));
        a.range.end = b.splitPosition.clone();
        a.range.end.stickiness = 'toPrevious';
        return [a, secondPart];
    }
    // The default case.
    //
    a.range = a.range._getTransformedBySplitOperation(b);
    return [a];
});
setTransformation(InsertOperation, AttributeOperation, (a, b) => {
    const result = [a];
    // Case 1:
    //
    // The attribute operation range includes the position where nodes were inserted.
    // There are two possible scenarios: the inserted nodes were text and they should receive attributes or
    // the inserted nodes were elements and they should not receive attributes.
    //
    // This is a mirror scenario to the one described in `AttributeOperation` x `InsertOperation` transformation,
    // although this case is a little less complicated. In this case we simply need to change attributes of the
    // inserted nodes and that's it.
    //
    if (a.shouldReceiveAttributes && a.position.hasSameParentAs(b.range.start) && b.range.containsPosition(a.position)) {
        const op = _getComplementaryAttributeOperations(a, b.key, b.newValue);
        if (op) {
            result.push(op);
        }
    }
    // The default case is: do nothing.
    // `AttributeOperation` does not change the model tree structure so `InsertOperation` does not need to be changed.
    //
    return result;
});
setTransformation(InsertOperation, InsertOperation, (a, b, context) => {
    // Case 1:
    //
    // Two insert operations insert nodes at the same position. Since they are the same, it needs to be decided
    // what will be the order of inserted nodes. However, there is no additional information to help in that
    // decision. Also, when `b` will be transformed by `a`, the same order must be maintained.
    //
    // To achieve that, we will check if the operation is strong.
    // If it is, it won't get transformed. If it is not, it will be moved.
    //
    if (a.position.isEqual(b.position) && context.aIsStrong) {
        return [a];
    }
    // The default case.
    //
    a.position = a.position._getTransformedByInsertOperation(b);
    return [a];
});
setTransformation(InsertOperation, MoveOperation, (a, b) => {
    // The default case.
    //
    a.position = a.position._getTransformedByMoveOperation(b);
    return [a];
});
setTransformation(InsertOperation, SplitOperation, (a, b) => {
    // The default case.
    //
    a.position = a.position._getTransformedBySplitOperation(b);
    return [a];
});
setTransformation(InsertOperation, MergeOperation, (a, b) => {
    a.position = a.position._getTransformedByMergeOperation(b);
    return [a];
});
// -----------------------
setTransformation(MarkerOperation, InsertOperation, (a, b) => {
    if (a.oldRange) {
        a.oldRange = a.oldRange._getTransformedByInsertOperation(b)[0];
    }
    if (a.newRange) {
        a.newRange = a.newRange._getTransformedByInsertOperation(b)[0];
    }
    return [a];
});
setTransformation(MarkerOperation, MarkerOperation, (a, b, context) => {
    if (a.name == b.name) {
        if (context.aIsStrong) {
            a.oldRange = b.newRange ? b.newRange.clone() : null;
        }
        else {
            return [new NoOperation(0)];
        }
    }
    return [a];
});
setTransformation(MarkerOperation, MergeOperation, (a, b) => {
    if (a.oldRange) {
        a.oldRange = a.oldRange._getTransformedByMergeOperation(b);
    }
    if (a.newRange) {
        a.newRange = a.newRange._getTransformedByMergeOperation(b);
    }
    return [a];
});
setTransformation(MarkerOperation, MoveOperation, (a, b, context) => {
    if (a.oldRange) {
        a.oldRange = Range._createFromRanges(a.oldRange._getTransformedByMoveOperation(b));
    }
    if (a.newRange) {
        if (context.abRelation) {
            const aNewRange = Range._createFromRanges(a.newRange._getTransformedByMoveOperation(b));
            if (context.abRelation.side == 'left' && b.targetPosition.isEqual(a.newRange.start)) {
                a.newRange.end = aNewRange.end;
                a.newRange.start.path = context.abRelation.path;
                return [a];
            }
            else if (context.abRelation.side == 'right' && b.targetPosition.isEqual(a.newRange.end)) {
                a.newRange.start = aNewRange.start;
                a.newRange.end.path = context.abRelation.path;
                return [a];
            }
        }
        a.newRange = Range._createFromRanges(a.newRange._getTransformedByMoveOperation(b));
    }
    return [a];
});
setTransformation(MarkerOperation, SplitOperation, (a, b, context) => {
    if (a.oldRange) {
        a.oldRange = a.oldRange._getTransformedBySplitOperation(b);
    }
    if (a.newRange) {
        if (context.abRelation) {
            const aNewRange = a.newRange._getTransformedBySplitOperation(b);
            if (a.newRange.start.isEqual(b.splitPosition) && context.abRelation.wasStartBeforeMergedElement) {
                a.newRange.start = Position._createAt(b.insertionPosition);
            }
            else if (a.newRange.start.isEqual(b.splitPosition) && !context.abRelation.wasInLeftElement) {
                a.newRange.start = Position._createAt(b.moveTargetPosition);
            }
            if (a.newRange.end.isEqual(b.splitPosition) && context.abRelation.wasInRightElement) {
                a.newRange.end = Position._createAt(b.moveTargetPosition);
            }
            else if (a.newRange.end.isEqual(b.splitPosition) && context.abRelation.wasEndBeforeMergedElement) {
                a.newRange.end = Position._createAt(b.insertionPosition);
            }
            else {
                a.newRange.end = aNewRange.end;
            }
            return [a];
        }
        a.newRange = a.newRange._getTransformedBySplitOperation(b);
    }
    return [a];
});
// -----------------------
setTransformation(MergeOperation, InsertOperation, (a, b) => {
    if (a.sourcePosition.hasSameParentAs(b.position)) {
        a.howMany += b.howMany;
    }
    a.sourcePosition = a.sourcePosition._getTransformedByInsertOperation(b);
    a.targetPosition = a.targetPosition._getTransformedByInsertOperation(b);
    return [a];
});
setTransformation(MergeOperation, MergeOperation, (a, b, context) => {
    // Case 1:
    //
    // Same merge operations.
    //
    // Both operations have same source and target positions. So the element already got merged and there is
    // theoretically nothing to do.
    //
    if (a.sourcePosition.isEqual(b.sourcePosition) && a.targetPosition.isEqual(b.targetPosition)) {
        // There are two ways that we can provide a do-nothing operation.
        //
        // First is simply a NoOperation instance. We will use it if `b` operation was not undone.
        //
        // Second is a merge operation that has the source operation in the merged element - in the graveyard -
        // same target position and `howMany` equal to `0`. So it is basically merging an empty element from graveyard
        // which is almost the same as NoOperation.
        //
        // This way the merge operation can be later transformed by split operation
        // to provide correct undo. This will be used if `b` operation was undone (only then it is correct).
        //
        if (!context.bWasUndone) {
            return [new NoOperation(0)];
        }
        else {
            const path = b.graveyardPosition.path.slice();
            path.push(0);
            a.sourcePosition = new Position(b.graveyardPosition.root, path);
            a.howMany = 0;
            return [a];
        }
    }
    // Case 2:
    //
    // Same merge source position but different target position.
    //
    // This can happen during collaboration. For example, if one client merged a paragraph to the previous paragraph
    // and the other person removed that paragraph and merged the same paragraph to something before:
    //
    // Client A:
    // <p>Foo</p><p>Bar</p><p>[]Xyz</p>
    // <p>Foo</p><p>BarXyz</p>
    //
    // Client B:
    // <p>Foo</p>[<p>Bar</p>]<p>Xyz</p>
    // <p>Foo</p><p>[]Xyz</p>
    // <p>FooXyz</p>
    //
    // In this case we need to decide where finally "Xyz" will land:
    //
    // <p>FooXyz</p>               graveyard: <p>Bar</p>
    // <p>Foo</p>                  graveyard: <p>BarXyz</p>
    //
    // Let's move it in a way so that a merge operation that does not target to graveyard is more important so that
    // nodes does not end up in the graveyard. It makes sense. Both for Client A and for Client B "Xyz" finally did not
    // end up in the graveyard (see above).
    //
    // If neither or both operations point to graveyard, then let `aIsStrong` decide.
    //
    if (a.sourcePosition.isEqual(b.sourcePosition) && !a.targetPosition.isEqual(b.targetPosition) &&
        !context.bWasUndone && context.abRelation != 'splitAtSource') {
        const aToGraveyard = a.targetPosition.root.rootName == '$graveyard';
        const bToGraveyard = b.targetPosition.root.rootName == '$graveyard';
        // If `aIsWeak` it means that `a` points to graveyard while `b` doesn't. Don't move nodes then.
        const aIsWeak = aToGraveyard && !bToGraveyard;
        // If `bIsWeak` it means that `b` points to graveyard while `a` doesn't. Force moving nodes then.
        const bIsWeak = bToGraveyard && !aToGraveyard;
        // Force move if `b` is weak or neither operation is weak but `a` is stronger through `context.aIsStrong`.
        const forceMove = bIsWeak || (!aIsWeak && context.aIsStrong);
        if (forceMove) {
            const sourcePosition = b.targetPosition._getTransformedByMergeOperation(b);
            const targetPosition = a.targetPosition._getTransformedByMergeOperation(b);
            return [new MoveOperation(sourcePosition, a.howMany, targetPosition, 0)];
        }
        else {
            return [new NoOperation(0)];
        }
    }
    // The default case.
    //
    if (a.sourcePosition.hasSameParentAs(b.targetPosition)) {
        a.howMany += b.howMany;
    }
    a.sourcePosition = a.sourcePosition._getTransformedByMergeOperation(b);
    a.targetPosition = a.targetPosition._getTransformedByMergeOperation(b);
    // Handle positions in graveyard.
    // If graveyard positions are same and `a` operation is strong - do not transform.
    if (!a.graveyardPosition.isEqual(b.graveyardPosition) || !context.aIsStrong) {
        a.graveyardPosition = a.graveyardPosition._getTransformedByMergeOperation(b);
    }
    return [a];
});
setTransformation(MergeOperation, MoveOperation, (a, b, context) => {
    // Case 1:
    //
    // The element to merge got removed.
    //
    // Merge operation does support merging elements which are not siblings. So it would not be a problem
    // from technical point of view. However, if the element was removed, the intention of the user deleting it
    // was to have it all deleted, together with its children. From user experience point of view, moving back the
    // removed nodes might be unexpected. This means that in this scenario we will block the merging.
    //
    // The exception of this rule would be if the remove operation was later undone.
    //
    const removedRange = Range._createFromPositionAndShift(b.sourcePosition, b.howMany);
    if (b.type == 'remove' && !context.bWasUndone && !context.forceWeakRemove) {
        if (a.deletionPosition.hasSameParentAs(b.sourcePosition) && removedRange.containsPosition(a.sourcePosition)) {
            return [new NoOperation(0)];
        }
    }
    // The default case.
    //
    if (a.sourcePosition.hasSameParentAs(b.targetPosition)) {
        a.howMany += b.howMany;
    }
    if (a.sourcePosition.hasSameParentAs(b.sourcePosition)) {
        a.howMany -= b.howMany;
    }
    a.sourcePosition = a.sourcePosition._getTransformedByMoveOperation(b);
    a.targetPosition = a.targetPosition._getTransformedByMoveOperation(b);
    // `MergeOperation` graveyard position is like `MoveOperation` target position. It is a position where element(s) will
    // be moved. Like in other similar cases, we need to consider the scenario when those positions are same.
    // Here, we will treat `MergeOperation` like it is always strong (see `InsertOperation` x `InsertOperation` for comparison).
    // This means that we won't transform graveyard position if it is equal to move operation target position.
    if (!a.graveyardPosition.isEqual(b.targetPosition)) {
        a.graveyardPosition = a.graveyardPosition._getTransformedByMoveOperation(b);
    }
    return [a];
});
setTransformation(MergeOperation, SplitOperation, (a, b, context) => {
    if (b.graveyardPosition) {
        // If `b` operation defines graveyard position, a node from graveyard will be moved. This means that we need to
        // transform `a.graveyardPosition` accordingly.
        a.graveyardPosition = a.graveyardPosition._getTransformedByDeletion(b.graveyardPosition, 1);
        // This is a scenario foreseen in `MergeOperation` x `MergeOperation`, with two identical merge operations.
        //
        // So, there was `MergeOperation` x `MergeOperation` transformation earlier. Now, `a` is a merge operation which
        // source position is in graveyard. Interestingly, split operation wants to use the node to be merged by `a`. This
        // means that `b` is undoing that merge operation from earlier, which caused `a` to be in graveyard.
        //
        // If that's the case, at this point, we will only "fix" `a.howMany`. It was earlier set to `0` in
        // `MergeOperation` x `MergeOperation` transformation. Later transformations in this function will change other
        // properties.
        //
        if (a.deletionPosition.isEqual(b.graveyardPosition)) {
            a.howMany = b.howMany;
        }
    }
    // Case 1:
    //
    // Merge operation moves nodes to the place where split happens.
    // This is a classic situation when there are two paragraphs, and there is a split (enter) after the first
    // paragraph and there is a merge (delete) at the beginning of the second paragraph:
    //
    // <p>Foo{}</p><p>[]Bar</p>.
    //
    // Split is after `Foo`, while merge is from `Bar` to the end of `Foo`.
    //
    // State after split:
    // <p>Foo</p><p></p><p>Bar</p>
    //
    // Now, `Bar` should be merged to the new paragraph:
    // <p>Foo</p><p>Bar</p>
    //
    // Instead of merging it to the original paragraph:
    // <p>FooBar</p><p></p>
    //
    // This means that `targetPosition` needs to be transformed. This is the default case though.
    // For example, if the split would be after `F`, `targetPosition` should also be transformed.
    //
    // There are three exceptions, though, when we want to keep `targetPosition` as it was.
    //
    // First exception is when the merge target position is inside an element (not at the end, as usual). This
    // happens when the merge operation earlier was transformed by "the same" merge operation. If merge operation
    // targets inside the element we want to keep the original target position (and not transform it) because
    // we have additional context telling us that we want to merge to the original element. We can check if the
    // merge operation points inside element by checking what is `SplitOperation#howMany`. Since merge target position
    // is same as split position, if `howMany` is non-zero, it means that the merge target position is inside an element.
    //
    // Second exception is when the element to merge is in the graveyard and split operation uses it. In that case
    // if target position would be transformed, the merge operation would target at the source position:
    //
    // root: <p>Foo</p>				graveyard: <p></p>
    //
    // SplitOperation: root [ 0, 3 ] using graveyard [ 0 ] (howMany = 0)
    // MergeOperation: graveyard [ 0, 0 ] -> root [ 0, 3 ] (howMany = 0)
    //
    // Since split operation moves the graveyard node back to the root, the merge operation source position changes.
    // We would like to merge from the empty <p> to the "Foo" <p>:
    //
    // root: <p>Foo</p><p></p>			graveyard:
    //
    // MergeOperation#sourcePosition = root [ 1, 0 ]
    //
    // If `targetPosition` is transformed, it would become root [ 1, 0 ] as well. It has to be kept as it was.
    //
    // Third exception is connected with relations. If this happens during undo and we have explicit information
    // that target position has not been affected by the operation which is undone by this split then this split should
    // not move the target position either.
    //
    if (a.targetPosition.isEqual(b.splitPosition)) {
        const mergeInside = b.howMany != 0;
        const mergeSplittingElement = b.graveyardPosition && a.deletionPosition.isEqual(b.graveyardPosition);
        if (mergeInside || mergeSplittingElement || context.abRelation == 'mergeTargetNotMoved') {
            a.sourcePosition = a.sourcePosition._getTransformedBySplitOperation(b);
            return [a];
        }
    }
    // Case 2:
    //
    // Merge source is at the same position as split position. This sometimes happen, mostly during undo.
    // The decision here is mostly to choose whether merge source position should stay where it is (so it will be at the end of the
    // split element) or should be move to the beginning of the new element.
    //
    if (a.sourcePosition.isEqual(b.splitPosition)) {
        // Use context to check if `SplitOperation` is not undoing a merge operation, that didn't change the `a` operation.
        // This scenario happens the undone merge operation moved nodes at the source position of `a` operation.
        // In that case `a` operation source position should stay where it is.
        if (context.abRelation == 'mergeSourceNotMoved') {
            a.howMany = 0;
            a.targetPosition = a.targetPosition._getTransformedBySplitOperation(b);
            return [a];
        }
        // This merge operation might have been earlier transformed by a merge operation which both merged the same element.
        // See that case in `MergeOperation` x `MergeOperation` transformation. In that scenario, if the merge operation has been undone,
        // the special case is not applied.
        //
        // Now, the merge operation is transformed by the split which has undone that previous merge operation.
        // So now we are fixing situation which was skipped in `MergeOperation` x `MergeOperation` case.
        //
        if (context.abRelation == 'mergeSameElement' || a.sourcePosition.offset > 0) {
            a.sourcePosition = b.moveTargetPosition.clone();
            a.targetPosition = a.targetPosition._getTransformedBySplitOperation(b);
            return [a];
        }
    }
    // The default case.
    //
    if (a.sourcePosition.hasSameParentAs(b.splitPosition)) {
        a.howMany = b.splitPosition.offset;
    }
    a.sourcePosition = a.sourcePosition._getTransformedBySplitOperation(b);
    a.targetPosition = a.targetPosition._getTransformedBySplitOperation(b);
    return [a];
});
// -----------------------
setTransformation(MoveOperation, InsertOperation, (a, b) => {
    const moveRange = Range._createFromPositionAndShift(a.sourcePosition, a.howMany);
    const transformed = moveRange._getTransformedByInsertOperation(b, false)[0];
    a.sourcePosition = transformed.start;
    a.howMany = transformed.end.offset - transformed.start.offset;
    // See `InsertOperation` x `MoveOperation` transformation for details on this case.
    //
    // In summary, both operations point to the same place, so the order of nodes needs to be decided.
    // `MoveOperation` is considered weaker, so it is always transformed, unless there was a certain relation
    // between operations.
    //
    if (!a.targetPosition.isEqual(b.position)) {
        a.targetPosition = a.targetPosition._getTransformedByInsertOperation(b);
    }
    return [a];
});
setTransformation(MoveOperation, MoveOperation, (a, b, context) => {
    //
    // Setting and evaluating some variables that will be used in special cases and default algorithm.
    //
    // Create ranges from `MoveOperations` properties.
    const rangeA = Range._createFromPositionAndShift(a.sourcePosition, a.howMany);
    const rangeB = Range._createFromPositionAndShift(b.sourcePosition, b.howMany);
    // Assign `context.aIsStrong` to a different variable, because the value may change during execution of
    // this algorithm and we do not want to override original `context.aIsStrong` that will be used in later transformations.
    let aIsStrong = context.aIsStrong;
    // This will be used to decide the order of nodes if both operations target at the same position.
    // By default, use strong/weak operation mechanism.
    let insertBefore = !context.aIsStrong;
    // If the relation is set, then use it to decide nodes order.
    if (context.abRelation == 'insertBefore' || context.baRelation == 'insertAfter') {
        insertBefore = true;
    }
    else if (context.abRelation == 'insertAfter' || context.baRelation == 'insertBefore') {
        insertBefore = false;
    }
    // `a.targetPosition` could be affected by the `b` operation. We will transform it.
    let newTargetPosition;
    if (a.targetPosition.isEqual(b.targetPosition) && insertBefore) {
        newTargetPosition = a.targetPosition._getTransformedByDeletion(b.sourcePosition, b.howMany);
    }
    else {
        newTargetPosition = a.targetPosition._getTransformedByMove(b.sourcePosition, b.targetPosition, b.howMany);
    }
    //
    // Special case #1 + mirror.
    //
    // Special case when both move operations' target positions are inside nodes that are
    // being moved by the other move operation. So in other words, we move ranges into inside of each other.
    // This case can't be solved reasonably (on the other hand, it should not happen often).
    if (_moveTargetIntoMovedRange(a, b) && _moveTargetIntoMovedRange(b, a)) {
        // Instead of transforming operation, we return a reverse of the operation that we transform by.
        // So when the results of this "transformation" will be applied, `b` MoveOperation will get reversed.
        return [b.getReversed()];
    }
    //
    // End of special case #1.
    //
    //
    // Special case #2.
    //
    // Check if `b` operation targets inside `rangeA`.
    const bTargetsToA = rangeA.containsPosition(b.targetPosition);
    // If `b` targets to `rangeA` and `rangeA` contains `rangeB`, `b` operation has no influence on `a` operation.
    // You might say that operation `b` is captured inside operation `a`.
    if (bTargetsToA && rangeA.containsRange(rangeB, true)) {
        // There is a mini-special case here, where `rangeB` is on other level than `rangeA`. That's why
        // we need to transform `a` operation anyway.
        rangeA.start = rangeA.start._getTransformedByMove(b.sourcePosition, b.targetPosition, b.howMany);
        rangeA.end = rangeA.end._getTransformedByMove(b.sourcePosition, b.targetPosition, b.howMany);
        return _makeMoveOperationsFromRanges([rangeA], newTargetPosition);
    }
    //
    // Special case #2 mirror.
    //
    const aTargetsToB = rangeB.containsPosition(a.targetPosition);
    if (aTargetsToB && rangeB.containsRange(rangeA, true)) {
        // `a` operation is "moved together" with `b` operation.
        // Here, just move `rangeA` "inside" `rangeB`.
        rangeA.start = rangeA.start._getCombined(b.sourcePosition, b.getMovedRangeStart());
        rangeA.end = rangeA.end._getCombined(b.sourcePosition, b.getMovedRangeStart());
        return _makeMoveOperationsFromRanges([rangeA], newTargetPosition);
    }
    //
    // End of special case #2.
    //
    //
    // Special case #3 + mirror.
    //
    // `rangeA` has a node which is an ancestor of `rangeB`. In other words, `rangeB` is inside `rangeA`
    // but not on the same tree level. In such case ranges have common part but we have to treat it
    // differently, because in such case those ranges are not really conflicting and should be treated like
    // two separate ranges. Also we have to discard two difference parts.
    const aCompB = compareArrays(a.sourcePosition.getParentPath(), b.sourcePosition.getParentPath());
    if (aCompB == 'prefix' || aCompB == 'extension') {
        // Transform `rangeA` by `b` operation and make operation out of it, and that's all.
        // Note that this is a simplified version of default case, but here we treat the common part (whole `rangeA`)
        // like a one difference part.
        rangeA.start = rangeA.start._getTransformedByMove(b.sourcePosition, b.targetPosition, b.howMany);
        rangeA.end = rangeA.end._getTransformedByMove(b.sourcePosition, b.targetPosition, b.howMany);
        return _makeMoveOperationsFromRanges([rangeA], newTargetPosition);
    }
    //
    // End of special case #3.
    //
    //
    // Default case - ranges are on the same level or are not connected with each other.
    //
    // Modifier for default case.
    // Modifies `aIsStrong` flag in certain conditions.
    //
    // If only one of operations is a remove operation, we force remove operation to be the "stronger" one
    // to provide more expected results.
    if (a.type == 'remove' && b.type != 'remove' && !context.aWasUndone && !context.forceWeakRemove) {
        aIsStrong = true;
    }
    else if (a.type != 'remove' && b.type == 'remove' && !context.bWasUndone && !context.forceWeakRemove) {
        aIsStrong = false;
    }
    // Handle operation's source ranges - check how `rangeA` is affected by `b` operation.
    // This will aggregate transformed ranges.
    const ranges = [];
    // Get the "difference part" of `a` operation source range.
    // This is an array with one or two ranges. Two ranges if `rangeB` is inside `rangeA`.
    const difference = rangeA.getDifference(rangeB);
    for (const range of difference) {
        // Transform those ranges by `b` operation. For example if `b` moved range from before those ranges, fix those ranges.
        range.start = range.start._getTransformedByDeletion(b.sourcePosition, b.howMany);
        range.end = range.end._getTransformedByDeletion(b.sourcePosition, b.howMany);
        // If `b` operation targets into `rangeA` on the same level, spread `rangeA` into two ranges.
        const shouldSpread = compareArrays(range.start.getParentPath(), b.getMovedRangeStart().getParentPath()) == 'same';
        const newRanges = range._getTransformedByInsertion(b.getMovedRangeStart(), b.howMany, shouldSpread);
        ranges.push(...newRanges);
    }
    // Then, we have to manage the "common part" of both move ranges.
    const common = rangeA.getIntersection(rangeB);
    if (common !== null && aIsStrong) {
        // Calculate the new position of that part of original range.
        common.start = common.start._getCombined(b.sourcePosition, b.getMovedRangeStart());
        common.end = common.end._getCombined(b.sourcePosition, b.getMovedRangeStart());
        // Take care of proper range order.
        //
        // Put `common` at appropriate place. Keep in mind that we are interested in original order.
        // Basically there are only three cases: there is zero, one or two difference ranges.
        //
        // If there is zero difference ranges, just push `common` in the array.
        if (ranges.length === 0) {
            ranges.push(common);
        }
        // If there is one difference range, we need to check whether common part was before it or after it.
        else if (ranges.length == 1) {
            if (rangeB.start.isBefore(rangeA.start) || rangeB.start.isEqual(rangeA.start)) {
                ranges.unshift(common);
            }
            else {
                ranges.push(common);
            }
        }
        // If there are more ranges (which means two), put common part between them. This is the only scenario
        // where there could be two difference ranges so we don't have to make any comparisons.
        else {
            ranges.splice(1, 0, common);
        }
    }
    if (ranges.length === 0) {
        // If there are no "source ranges", nothing should be changed.
        // Note that this can happen only if `aIsStrong == false` and `rangeA.isEqual( rangeB )`.
        return [new NoOperation(a.baseVersion)];
    }
    return _makeMoveOperationsFromRanges(ranges, newTargetPosition);
});
setTransformation(MoveOperation, SplitOperation, (a, b, context) => {
    let newTargetPosition = a.targetPosition.clone();
    // Do not transform if target position is same as split insertion position and this split comes from undo.
    // This should be done on relations but it is too much work for now as it would require relations working in collaboration.
    // We need to make a decision how we will resolve such conflict and this is less harmful way.
    if (!a.targetPosition.isEqual(b.insertionPosition) || !b.graveyardPosition || context.abRelation == 'moveTargetAfter') {
        newTargetPosition = a.targetPosition._getTransformedBySplitOperation(b);
    }
    // Case 1:
    //
    // Last element in the moved range got split.
    //
    // In this case the default range transformation will not work correctly as the element created by
    // split operation would be outside the range. The range to move needs to be fixed manually.
    //
    const moveRange = Range._createFromPositionAndShift(a.sourcePosition, a.howMany);
    if (moveRange.end.isEqual(b.insertionPosition)) {
        // Do it only if this is a "natural" split, not a one that comes from undo.
        // If this is undo split, only `targetPosition` needs to be changed (if the move is a remove).
        if (!b.graveyardPosition) {
            a.howMany++;
        }
        a.targetPosition = newTargetPosition;
        return [a];
    }
    // Case 2:
    //
    // Split happened between the moved nodes. In this case two ranges to move need to be generated.
    //
    // Characters `ozba` are moved to the end of paragraph `Xyz` but split happened.
    // <p>F[oz|ba]r</p><p>Xyz</p>
    //
    // After split:
    // <p>F[oz</p><p>ba]r</p><p>Xyz</p>
    //
    // Correct ranges:
    // <p>F[oz]</p><p>[ba]r</p><p>Xyz</p>
    //
    // After move:
    // <p>F</p><p>r</p><p>Xyzozba</p>
    //
    if (moveRange.start.hasSameParentAs(b.splitPosition) && moveRange.containsPosition(b.splitPosition)) {
        let rightRange = new Range(b.splitPosition, moveRange.end);
        rightRange = rightRange._getTransformedBySplitOperation(b);
        const ranges = [
            new Range(moveRange.start, b.splitPosition),
            rightRange
        ];
        return _makeMoveOperationsFromRanges(ranges, newTargetPosition);
    }
    // Case 3:
    //
    // Move operation targets at the split position. We need to decide if the nodes should be inserted
    // at the end of the split element or at the beginning of the new element.
    //
    if (a.targetPosition.isEqual(b.splitPosition) && context.abRelation == 'insertAtSource') {
        newTargetPosition = b.moveTargetPosition;
    }
    // Case 4:
    //
    // Move operation targets just after the split element. We need to decide if the nodes should be inserted
    // between two parts of split element, or after the new element.
    //
    // Split at `|`, while move operation moves `<p>Xyz</p>` and targets at `^`:
    // <p>Foo|bar</p>^<p>baz</p>
    // <p>Foo</p>^<p>bar</p><p>baz</p> or <p>Foo</p><p>bar</p>^<p>baz</p>?
    //
    // If there is no contextual information between operations (for example, they come from collaborative
    // editing), we don't want to put some unrelated content (move) between parts of related content (split parts).
    // However, if the split is from undo, in the past, the moved content might be targeting between the
    // split parts, meaning that was exactly user's intention:
    //
    // <p>Foo</p>^<p>bar</p>		<--- original situation, in "past".
    // <p>Foobar</p>^				<--- after merge target position is transformed.
    // <p>Foo|bar</p>^				<--- then the merge is undone, and split happens, which leads us to current situation.
    //
    // In this case it is pretty clear that the intention was to put new paragraph between those nodes,
    // so we need to transform accordingly. We can detect this scenario thanks to relations.
    //
    if (a.targetPosition.isEqual(b.insertionPosition) && context.abRelation == 'insertBetween') {
        newTargetPosition = a.targetPosition;
    }
    // The default case.
    //
    const transformed = moveRange._getTransformedBySplitOperation(b);
    const ranges = [transformed];
    // Case 5:
    //
    // Moved range contains graveyard element used by split operation. Add extra move operation to the result.
    //
    if (b.graveyardPosition) {
        const movesGraveyardElement = moveRange.start.isEqual(b.graveyardPosition) || moveRange.containsPosition(b.graveyardPosition);
        if (a.howMany > 1 && movesGraveyardElement && !context.aWasUndone) {
            ranges.push(Range._createFromPositionAndShift(b.insertionPosition, 1));
        }
    }
    return _makeMoveOperationsFromRanges(ranges, newTargetPosition);
});
setTransformation(MoveOperation, MergeOperation, (a, b, context) => {
    const movedRange = Range._createFromPositionAndShift(a.sourcePosition, a.howMany);
    if (b.deletionPosition.hasSameParentAs(a.sourcePosition) && movedRange.containsPosition(b.sourcePosition)) {
        if (a.type == 'remove' && !context.forceWeakRemove) {
            // Case 1:
            //
            // The element to remove got merged.
            //
            // Merge operation does support merging elements which are not siblings. So it would not be a problem
            // from technical point of view. However, if the element was removed, the intention of the user
            // deleting it was to have it all deleted. From user experience point of view, moving back the
            // removed nodes might be unexpected. This means that in this scenario we will reverse merging and remove the element.
            //
            if (!context.aWasUndone) {
                const results = [];
                let gyMoveSource = b.graveyardPosition.clone();
                let splitNodesMoveSource = b.targetPosition._getTransformedByMergeOperation(b);
                if (a.howMany > 1) {
                    results.push(new MoveOperation(a.sourcePosition, a.howMany - 1, a.targetPosition, 0));
                    gyMoveSource = gyMoveSource._getTransformedByMove(a.sourcePosition, a.targetPosition, a.howMany - 1);
                    splitNodesMoveSource = splitNodesMoveSource._getTransformedByMove(a.sourcePosition, a.targetPosition, a.howMany - 1);
                }
                const gyMoveTarget = b.deletionPosition._getCombined(a.sourcePosition, a.targetPosition);
                const gyMove = new MoveOperation(gyMoveSource, 1, gyMoveTarget, 0);
                const splitNodesMoveTargetPath = gyMove.getMovedRangeStart().path.slice();
                splitNodesMoveTargetPath.push(0);
                const splitNodesMoveTarget = new Position(gyMove.targetPosition.root, splitNodesMoveTargetPath);
                splitNodesMoveSource = splitNodesMoveSource._getTransformedByMove(gyMoveSource, gyMoveTarget, 1);
                const splitNodesMove = new MoveOperation(splitNodesMoveSource, b.howMany, splitNodesMoveTarget, 0);
                results.push(gyMove);
                results.push(splitNodesMove);
                return results;
            }
        }
        else {
            // Case 2:
            //
            // The element to move got merged and it was the only element to move.
            // In this case just don't do anything, leave the node in the graveyard. Without special case
            // it would be a move operation that moves 0 nodes, so maybe it is better just to return no-op.
            //
            if (a.howMany == 1) {
                if (!context.bWasUndone) {
                    return [new NoOperation(0)];
                }
                else {
                    a.sourcePosition = b.graveyardPosition.clone();
                    a.targetPosition = a.targetPosition._getTransformedByMergeOperation(b);
                    return [a];
                }
            }
        }
    }
    // The default case.
    //
    const moveRange = Range._createFromPositionAndShift(a.sourcePosition, a.howMany);
    const transformed = moveRange._getTransformedByMergeOperation(b);
    a.sourcePosition = transformed.start;
    a.howMany = transformed.end.offset - transformed.start.offset;
    a.targetPosition = a.targetPosition._getTransformedByMergeOperation(b);
    return [a];
});
// -----------------------
setTransformation(RenameOperation, InsertOperation, (a, b) => {
    a.position = a.position._getTransformedByInsertOperation(b);
    return [a];
});
setTransformation(RenameOperation, MergeOperation, (a, b) => {
    // Case 1:
    //
    // Element to rename got merged, so it was moved to `b.graveyardPosition`.
    //
    if (a.position.isEqual(b.deletionPosition)) {
        a.position = b.graveyardPosition.clone();
        a.position.stickiness = 'toNext';
        return [a];
    }
    a.position = a.position._getTransformedByMergeOperation(b);
    return [a];
});
setTransformation(RenameOperation, MoveOperation, (a, b) => {
    a.position = a.position._getTransformedByMoveOperation(b);
    return [a];
});
setTransformation(RenameOperation, RenameOperation, (a, b, context) => {
    if (a.position.isEqual(b.position)) {
        if (context.aIsStrong) {
            a.oldName = b.newName;
        }
        else {
            return [new NoOperation(0)];
        }
    }
    return [a];
});
setTransformation(RenameOperation, SplitOperation, (a, b) => {
    // Case 1:
    //
    // The element to rename has been split. In this case, the new element should be also renamed.
    //
    // User decides to change the paragraph to a list item:
    // <paragraph>Foobar</paragraph>
    //
    // However, in meantime, split happens:
    // <paragraph>Foo</paragraph><paragraph>bar</paragraph>
    //
    // As a result, rename both elements:
    // <listItem>Foo</listItem><listItem>bar</listItem>
    //
    const renamePath = a.position.path;
    const splitPath = b.splitPosition.getParentPath();
    if (compareArrays(renamePath, splitPath) == 'same' && !b.graveyardPosition) {
        const extraRename = new RenameOperation(a.position.getShiftedBy(1), a.oldName, a.newName, 0);
        return [a, extraRename];
    }
    // The default case.
    //
    a.position = a.position._getTransformedBySplitOperation(b);
    return [a];
});
// -----------------------
setTransformation(RootAttributeOperation, RootAttributeOperation, (a, b, context) => {
    if (a.root === b.root && a.key === b.key) {
        if (!context.aIsStrong || a.newValue === b.newValue) {
            return [new NoOperation(0)];
        }
        else {
            a.oldValue = b.newValue;
        }
    }
    return [a];
});
// -----------------------
setTransformation(RootOperation, RootOperation, (a, b) => {
    if (a.rootName === b.rootName && a.isAdd === b.isAdd) {
        return [new NoOperation(0)];
    }
    return [a];
});
// -----------------------
setTransformation(SplitOperation, InsertOperation, (a, b) => {
    // The default case.
    //
    if (a.splitPosition.hasSameParentAs(b.position) && a.splitPosition.offset < b.position.offset) {
        a.howMany += b.howMany;
    }
    a.splitPosition = a.splitPosition._getTransformedByInsertOperation(b);
    a.insertionPosition = a.insertionPosition._getTransformedByInsertOperation(b);
    return [a];
});
setTransformation(SplitOperation, MergeOperation, (a, b, context) => {
    // Case 1:
    //
    // Split element got merged. If two different elements were merged, clients will have different content.
    //
    // Example. Merge at `{}`, split at `[]`:
    // <heading>Foo</heading>{}<paragraph>B[]ar</paragraph>
    //
    // On merge side it will look like this:
    // <heading>FooB[]ar</heading>
    // <heading>FooB</heading><heading>ar</heading>
    //
    // On split side it will look like this:
    // <heading>Foo</heading>{}<paragraph>B</paragraph><paragraph>ar</paragraph>
    // <heading>FooB</heading><paragraph>ar</paragraph>
    //
    // Clearly, the second element is different for both clients.
    //
    // We could use the removed merge element from graveyard as a split element but then clients would have a different
    // model state (in graveyard), because the split side client would still have an element in graveyard (removed by merge).
    //
    // To overcome this, in `SplitOperation` x `MergeOperation` transformation we will add additional `SplitOperation`
    // in the graveyard, which will actually clone the merged-and-deleted element. Then, that cloned element will be
    // used for splitting. Example below.
    //
    // Original state:
    // <heading>Foo</heading>{}<paragraph>B[]ar</paragraph>
    //
    // Merge side client:
    //
    // After merge:
    // <heading>FooB[]ar</heading>                                 graveyard: <paragraph></paragraph>
    //
    // Extra split:
    // <heading>FooB[]ar</heading>                                 graveyard: <paragraph></paragraph><paragraph></paragraph>
    //
    // Use the "cloned" element from graveyard:
    // <heading>FooB</heading><paragraph>ar</paragraph>            graveyard: <paragraph></paragraph>
    //
    // Split side client:
    //
    // After split:
    // <heading>Foo</heading>{}<paragraph>B</paragraph><paragraph>ar</paragraph>
    //
    // After merge:
    // <heading>FooB</heading><paragraph>ar</paragraph>            graveyard: <paragraph></paragraph>
    //
    // This special case scenario only applies if the original split operation clones the split element.
    // If the original split operation has `graveyardPosition` set, it all doesn't have sense because split operation
    // knows exactly which element it should use. So there would be no original problem with different contents.
    //
    // Additionally, the special case applies only if the merge wasn't already undone.
    //
    if (!a.graveyardPosition && !context.bWasUndone && a.splitPosition.hasSameParentAs(b.sourcePosition)) {
        const splitPath = b.graveyardPosition.path.slice();
        splitPath.push(0);
        const splitPosition = new Position(b.graveyardPosition.root, splitPath);
        const insertionPosition = SplitOperation.getInsertionPosition(new Position(b.graveyardPosition.root, splitPath));
        const additionalSplit = new SplitOperation(splitPosition, 0, insertionPosition, null, 0);
        a.splitPosition = a.splitPosition._getTransformedByMergeOperation(b);
        a.insertionPosition = SplitOperation.getInsertionPosition(a.splitPosition);
        a.graveyardPosition = additionalSplit.insertionPosition.clone();
        a.graveyardPosition.stickiness = 'toNext';
        return [additionalSplit, a];
    }
    // The default case.
    //
    if (a.splitPosition.hasSameParentAs(b.deletionPosition) && !a.splitPosition.isAfter(b.deletionPosition)) {
        a.howMany--;
    }
    if (a.splitPosition.hasSameParentAs(b.targetPosition)) {
        a.howMany += b.howMany;
    }
    a.splitPosition = a.splitPosition._getTransformedByMergeOperation(b);
    a.insertionPosition = SplitOperation.getInsertionPosition(a.splitPosition);
    if (a.graveyardPosition) {
        a.graveyardPosition = a.graveyardPosition._getTransformedByMergeOperation(b);
    }
    return [a];
});
setTransformation(SplitOperation, MoveOperation, (a, b, context) => {
    const rangeToMove = Range._createFromPositionAndShift(b.sourcePosition, b.howMany);
    if (a.graveyardPosition) {
        // Case 1:
        //
        // Split operation graveyard node was moved. In this case move operation is stronger. Since graveyard element
        // is already moved to the correct position, we need to only move the nodes after the split position.
        // This will be done by `MoveOperation` instead of `SplitOperation`.
        //
        const gyElementMoved = rangeToMove.start.isEqual(a.graveyardPosition) || rangeToMove.containsPosition(a.graveyardPosition);
        if (!context.bWasUndone && gyElementMoved) {
            const sourcePosition = a.splitPosition._getTransformedByMoveOperation(b);
            const newParentPosition = a.graveyardPosition._getTransformedByMoveOperation(b);
            const newTargetPath = newParentPosition.path.slice();
            newTargetPath.push(0);
            const newTargetPosition = new Position(newParentPosition.root, newTargetPath);
            const moveOp = new MoveOperation(sourcePosition, a.howMany, newTargetPosition, 0);
            return [moveOp];
        }
        a.graveyardPosition = a.graveyardPosition._getTransformedByMoveOperation(b);
    }
    // Case 2:
    //
    // Split is at a position where nodes were moved.
    //
    // This is a scenario described in `MoveOperation` x `SplitOperation` transformation but from the
    // "split operation point of view".
    //
    const splitAtTarget = a.splitPosition.isEqual(b.targetPosition);
    if (splitAtTarget && (context.baRelation == 'insertAtSource' || context.abRelation == 'splitBefore')) {
        a.howMany += b.howMany;
        a.splitPosition = a.splitPosition._getTransformedByDeletion(b.sourcePosition, b.howMany);
        a.insertionPosition = SplitOperation.getInsertionPosition(a.splitPosition);
        return [a];
    }
    if (splitAtTarget && context.abRelation && context.abRelation.howMany) {
        const { howMany, offset } = context.abRelation;
        a.howMany += howMany;
        a.splitPosition = a.splitPosition.getShiftedBy(offset);
        return [a];
    }
    // Case 3:
    //
    // If the split position is inside the moved range, we need to shift the split position to a proper place.
    // The position cannot be moved together with moved range because that would result in splitting of an incorrect element.
    //
    // Characters `bc` should be moved to the second paragraph while split position is between them:
    // <paragraph>A[b|c]d</paragraph><paragraph>Xyz</paragraph>
    //
    // After move, new split position is incorrect:
    // <paragraph>Ad</paragraph><paragraph>Xb|cyz</paragraph>
    //
    // Correct split position:
    // <paragraph>A|d</paragraph><paragraph>Xbcyz</paragraph>
    //
    // After split:
    // <paragraph>A</paragraph><paragraph>d</paragraph><paragraph>Xbcyz</paragraph>
    //
    if (a.splitPosition.hasSameParentAs(b.sourcePosition) && rangeToMove.containsPosition(a.splitPosition)) {
        const howManyRemoved = b.howMany - (a.splitPosition.offset - b.sourcePosition.offset);
        a.howMany -= howManyRemoved;
        if (a.splitPosition.hasSameParentAs(b.targetPosition) && a.splitPosition.offset < b.targetPosition.offset) {
            a.howMany += b.howMany;
        }
        a.splitPosition = b.sourcePosition.clone();
        a.insertionPosition = SplitOperation.getInsertionPosition(a.splitPosition);
        return [a];
    }
    // The default case.
    // Don't change `howMany` if move operation does not really move anything.
    //
    if (!b.sourcePosition.isEqual(b.targetPosition)) {
        if (a.splitPosition.hasSameParentAs(b.sourcePosition) && a.splitPosition.offset <= b.sourcePosition.offset) {
            a.howMany -= b.howMany;
        }
        if (a.splitPosition.hasSameParentAs(b.targetPosition) && a.splitPosition.offset < b.targetPosition.offset) {
            a.howMany += b.howMany;
        }
    }
    // Change position stickiness to force a correct transformation.
    a.splitPosition.stickiness = 'toNone';
    a.splitPosition = a.splitPosition._getTransformedByMoveOperation(b);
    a.splitPosition.stickiness = 'toNext';
    if (a.graveyardPosition) {
        a.insertionPosition = a.insertionPosition._getTransformedByMoveOperation(b);
    }
    else {
        a.insertionPosition = SplitOperation.getInsertionPosition(a.splitPosition);
    }
    return [a];
});
setTransformation(SplitOperation, SplitOperation, (a, b, context) => {
    // Case 1:
    //
    // Split at the same position.
    //
    // If there already was a split at the same position as in `a` operation, it means that the intention
    // conveyed by `a` operation has already been fulfilled and `a` should not do anything (to avoid double split).
    //
    // However, there is a difference if these are new splits or splits created by undo. These have different
    // intentions. Also splits moving back different elements from graveyard have different intentions. They
    // are just different operations.
    //
    // So we cancel split operation only if it was really identical.
    //
    // Also, there is additional case, where split operations aren't identical and should not be cancelled, however the
    // default transformation is incorrect too.
    //
    if (a.splitPosition.isEqual(b.splitPosition)) {
        if (!a.graveyardPosition && !b.graveyardPosition) {
            return [new NoOperation(0)];
        }
        if (a.graveyardPosition && b.graveyardPosition && a.graveyardPosition.isEqual(b.graveyardPosition)) {
            return [new NoOperation(0)];
        }
        // Use context to know that the `a.splitPosition` should stay where it is.
        // This happens during undo when first a merge operation moved nodes to `a.splitPosition` and now `b` operation undoes that merge.
        if (context.abRelation == 'splitBefore') {
            // Since split is at the same position, there are no nodes left to split.
            a.howMany = 0;
            // Note: there was `if ( a.graveyardPosition )` here but it was uncovered in tests and I couldn't find any scenarios for now.
            // That would have to be a `SplitOperation` that didn't come from undo but is transformed by operations that were undone.
            // It could happen if `context` is enabled in collaboration.
            a.graveyardPosition = a.graveyardPosition._getTransformedBySplitOperation(b);
            return [a];
        }
    }
    // Case 2:
    //
    // Same node is using to split different elements. This happens in undo when previously same element was merged to
    // two different elements. This is described in `MergeOperation` x `MergeOperation` transformation.
    //
    // In this case we will follow the same logic. We will assume that `insertionPosition` is same for both
    // split operations. This might not always be true but in the real cases that were experienced it was. After all,
    // if these splits are reverses of merge operations that were merging the same element, then the `insertionPosition`
    // should be same for both of those splits.
    //
    // Again, we will decide which operation is stronger by checking if split happens in graveyard or in non-graveyard root.
    //
    if (a.graveyardPosition && b.graveyardPosition && a.graveyardPosition.isEqual(b.graveyardPosition)) {
        const aInGraveyard = a.splitPosition.root.rootName == '$graveyard';
        const bInGraveyard = b.splitPosition.root.rootName == '$graveyard';
        // If `aIsWeak` it means that `a` points to graveyard while `b` doesn't. Don't move nodes then.
        const aIsWeak = aInGraveyard && !bInGraveyard;
        // If `bIsWeak` it means that `b` points to graveyard while `a` doesn't. Force moving nodes then.
        const bIsWeak = bInGraveyard && !aInGraveyard;
        // Force move if `b` is weak or neither operation is weak but `a` is stronger through `context.aIsStrong`.
        const forceMove = bIsWeak || (!aIsWeak && context.aIsStrong);
        if (forceMove) {
            const result = [];
            // First we need to move any nodes split by `b` back to where they were.
            // Do it only if `b` actually moved something.
            if (b.howMany) {
                result.push(new MoveOperation(b.moveTargetPosition, b.howMany, b.splitPosition, 0));
            }
            // Then we need to move nodes from `a` split position to their new element.
            // Do it only if `a` actually should move something.
            if (a.howMany) {
                result.push(new MoveOperation(a.splitPosition, a.howMany, a.moveTargetPosition, 0));
            }
            return result;
        }
        else {
            return [new NoOperation(0)];
        }
    }
    if (a.graveyardPosition) {
        a.graveyardPosition = a.graveyardPosition._getTransformedBySplitOperation(b);
    }
    // Case 3:
    //
    // Position where operation `b` inserted a new node after split is the same as the operation `a` split position.
    // As in similar cases, there is ambiguity if the split should be before the new node (created by `b`) or after.
    //
    if (a.splitPosition.isEqual(b.insertionPosition) && context.abRelation == 'splitBefore') {
        a.howMany++;
        return [a];
    }
    // Case 4:
    //
    // This is a mirror to the case 2. above.
    //
    if (b.splitPosition.isEqual(a.insertionPosition) && context.baRelation == 'splitBefore') {
        const newPositionPath = b.insertionPosition.path.slice();
        newPositionPath.push(0);
        const newPosition = new Position(b.insertionPosition.root, newPositionPath);
        const moveOp = new MoveOperation(a.insertionPosition, 1, newPosition, 0);
        return [a, moveOp];
    }
    // The default case.
    //
    if (a.splitPosition.hasSameParentAs(b.splitPosition) && a.splitPosition.offset < b.splitPosition.offset) {
        a.howMany -= b.howMany;
    }
    a.splitPosition = a.splitPosition._getTransformedBySplitOperation(b);
    a.insertionPosition = SplitOperation.getInsertionPosition(a.splitPosition);
    return [a];
});
/**
 * Checks whether `MoveOperation` `targetPosition` is inside a node from the moved range of the other `MoveOperation`.
 */
function _moveTargetIntoMovedRange(a, b) {
    return a.targetPosition._getTransformedByDeletion(b.sourcePosition, b.howMany) === null;
}
/**
 * Helper function for `MoveOperation` x `MoveOperation` transformation. Converts given ranges and target position to
 * move operations and returns them.
 *
 * Ranges and target position will be transformed on-the-fly when generating operations.
 *
 * Given `ranges` should be in the order of how they were in the original transformed operation.
 *
 * Given `targetPosition` is the target position of the first range from `ranges`.
 */
function _makeMoveOperationsFromRanges(ranges, targetPosition) {
    // At this moment we have some ranges and a target position, to which those ranges should be moved.
    // Order in `ranges` array is the go-to order of after transformation.
    //
    // We are almost done. We have `ranges` and `targetPosition` to make operations from.
    // Unfortunately, those operations may affect each other. Precisely, first operation after move
    // may affect source range and target position of second and third operation. Same with second
    // operation affecting third.
    //
    // We need to fix those source ranges and target positions once again, before converting `ranges` to operations.
    const operations = [];
    // Keep in mind that nothing will be transformed if there is just one range in `ranges`.
    for (let i = 0; i < ranges.length; i++) {
        // Create new operation out of a range and target position.
        const range = ranges[i];
        const op = new MoveOperation(range.start, range.end.offset - range.start.offset, targetPosition, 0);
        operations.push(op);
        // Transform other ranges by the generated operation.
        for (let j = i + 1; j < ranges.length; j++) {
            // All ranges in `ranges` array should be:
            //
            // * non-intersecting (these are part of original operation source range), and
            // * `targetPosition` does not target into them (opposite would mean that transformed operation targets "inside itself").
            //
            // This means that the transformation will be "clean" and always return one result.
            ranges[j] = ranges[j]._getTransformedByMove(op.sourcePosition, op.targetPosition, op.howMany)[0];
        }
        targetPosition = targetPosition._getTransformedByMove(op.sourcePosition, op.targetPosition, op.howMany);
    }
    return operations;
}
